COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.xgp
C00112 00003	ββ
C00113 ENDMK
C⊗;
.xgp
.FONT 0 30VR
.FONT 1 30VRI
.FONT 2 37VRB
.FONT 3 S30GRK
.squish
.script 5
.tabfnt 0
.adjust
.twinch 6.0
.he1
Analysis of Contour
.he2
∞
.sp 3
.center
ε2ANALYSIS OF OCCLUDING CONTOUR
.sp 2
.center
by
.sp 2
.center
D. Marr
.sp 4
.center
Draft IIε0
.sp 6
.single
ε1Summaryε0.  Almost nothing can be deduced about a general surface
given only its occluding contours in an image, yet contour information is easily
and effectively used by us to infer the shape of a surface.  Therefore,
implicit in the perceptual analysis of occluding contour must
lie various assumptions about
the viewed surfaces.  The assumptions that seem most natural are (a)
that the distinction between convex and concave segments
reflects real properties of the viewed surface; and (b) that contiguous
portions of contour arise from contiguous parts of the viewed surface --
i.e., there are no invisible obscuring edges.  It is proved that, for smooth surfaces,
these assumptions are essentially equivalent to assuming that the viewed surface is a
generalized cone.  Methods are defined for finding the axis of such a
cone, and for segmenting a surface constructed of several cones into its
components, whose axes can then be found separately.  These methods,
together with the algorithms for implementing them devised by Vatan & Marr (1976),
provide one link between an uninterpreted figure extracted from an image,
and the 3-D representation theory of Marr & Nishihara (1976).
.pa
.double
.center
ε2Introductionε0
    When one views a lithograph like "Rites of Spring" by P. Picasso (1959, see figure 
RITES) for the first time,
one immediately perceives it as the image of very particular three-dimensional surfaces.
This is a remarkable phenomenon, because the silhouettes could have been
generated by an infinite variety of shapes which, from other viewpoints,
would have no discernable similarities.  One can perhaps attribute part
of the phenomenon to an ε1a prioriε0 knowledge of the shapes that are depicted; but
not all of it, because one can use the medium of a silhouette to convey
a new shape, and because even with considerable effort it is difficult
to imagine the more bizarre three-dimensional surfaces that could have
given rise to the same silhouettes.
.center
(figure RITES near here)
    The analysis of silhouette is not merely a small and specialized
problem.  The contours that compose one correspond to occluding contours
in a more complete image. Such contours form a large fraction of an
artist's sketch, and they probably convey considerable information about
shape in normal images. Yet by itself, the shape of an occluding contour
carries very little information about the surface that generated it. For
example, neighbouring points on such a contour can arise from widely
separated points on the original surface.
    The interpretation of an occluding contour must therefore rest
upon a number of ε1a prioriε0 assumptions. If a surface is presented
that violates them, its interpretation will prove incorrect.
Shadowgraphs provide a case in point, where the appropriate arrangement
of one's hands can, to the surprise and delight of a child, produce the
shadow of a duck or rabbit despite its clear three-dimensional dissimilarity.
    This article therefore addresses the following question. Given
that some assumptions are necessary before the analysis of occluding
contour can begin, what assumptions is it reasonable to make, and what
do those assumptions mean in terms of the structure of the
three-dimensional surfaces being viewed?  I shall argue that it is
reasonable to assume continuity, and that the distinction between
convexities and concavities in a contour reflect real properties of the
viewed surface. It will be proved that these assumptions, together with
others of an essentially technical nature, are equivalent to assuming
that the viewed surface is a generalized cone.
    The second part of the article assumes that a surface is composed
of generalized cones, and establishes a number of results about the
images of the axes of these cones and of the joins between them. These results
lead to methods for interpreting occluding contours in views of objects
composed of generalized cones, provided that no axis appears severely
foreshortened in the image.  Vatan & Marr (1976) derive algorithms that
implement these methods, and exhibit the results of applying them to a
number of natural images.
.block 4
.center
(figure DIAGRAM near here)
.center
ε2The basic hypothesesε0
    Suppose that ε3sε0 is an arbitrary three-dimensional surface,
and that ε1sε0 is its image as produced by the projection ε3iε0:
ε3sε0 ----> ε1sε0.  ε1sε0 has a bounding contour ε1cε0 say,
that corresponds to the silhouette of ε3sε0, and which we can think of
as having been obtained by acting on ε1sε0 with a boundary operator ∂
(see figure DIAGRAM).
.br
.twinch 5.0
ε1Definitionε0. Let ε3gε0 be the set of points on ε3sε0 whose
image lies on ε1cε0. Then ε3gε0 is called the ε1contour
generatorε0 of ε1cε0 on ε3sε0.
.twinch 6.0
.br
That is, ε3gε0 is the set of points ε1Pε0 on ε3sε0 such that
ε3iε1(P)ε0 lies on ε1cε0.  We can now define the operator ε3dε0:
ε3dε1(ε3sε1)ε0 = ε3gε0 which is induced by ∂, and which selects
ε3gε0 out of ε3sε0.  This is illustrated in figure DIAGRAM, where
∂ is defined is such a way that ε3idε0 = ∂ε3iε0.  Notice that
ε3iε0, ε3dε0, ε1c, sε0 and ε3gε0 all depend upon the position
from which ε3sε0 is viewed.
    We now discuss various restrictions that may be placed on the
mappings in figure DIAGRAM.
.br
  ε1Restriction R1: ε3sε1 is everywhere twice differentiable with
continuous second derivative.ε0
.br
This restriction is of only technical importance.  We shall need to be
able to distinguish convex pieces of contour from concave, and it is
easiest to do so if the second derivative of ε3sε0, and hence of
ε1cε0, is defined.  If ε1cε0 were piecewise linear, the notions of
convex and concave would still have meaning, but it is unnecessarily
tedious to include this case. Provided that ε3sε0 is continuous, we
can construct an approximation ε3tε0 that stays within ε3eε0 of
ε3sε0 and which has continuous second derivative (by the
Stone-Weierstrass theorem). The convenience of ε1R1ε0 is therefore
obtained without important loss of generality.
.br
  ε1Restriction R2: The inverse ε3iε0-1↔ε1 : ε1cε1 ----> ε3gε1 is one-valued.ε0
.br
The second condition is more of a technical convenience than a
substantial restriction, but perhaps less obviously so. It requires
that, for a given viewing angle, the contour generator ε3ε0 is
one-dimensional rather than two. Each line of sight to the boundary
ε3gε0 on ε3sε0 must intersect ε3sε0 at only one point, not for
example along a line.  One can usually prevent the line of sight
intersecting the surface in a line by deforming it slightly, but
ε1R2ε0 is somewhat stronger than this, since it forbids the situation
where the line of sight grazes the surface ε3sε0 twice. In practise,
ε1R2ε0 amounts to some kind of convexity condition on ε3sε0. It will not usually
be imposed for all viewing angles, and when it is imposed, we shall see
that there are ways of regaining most of the generality that it excludes.
.center
(figure HILLS near here)
.br
  ε1Restriction R3: The inverse ε3iε0-1↔ε1 : c ----> ε3gε1 is continuous.ε0
.br
This condition is a powerful one. Together with ε1R2ε0, it implies
that the contour generator ε3gε0 is a continuous curve across ε3sε0
-- i.e. that it does not jump erratically from place to place on
ε3sε0. For example, suppose that the contour ε1abε0 of figure HILLS
really arose from two hills, but the dotted portion of ε1bε0 happened
to be invisible. The the contour generator of ε1abε0 would be
discontinuous at ε1Pε0, where it leaps from one hill to the next.
This would violate ε1R3ε0, which is essentially equivalent to assuming
that the image of ε3sε0 contains no invisible obscuring edges.
ε1R3ε0 is a strong condition, but without it one can say almost
nothing about ε3sε0. Furthermore it is obeyed by most real-world images.
I know of no way to proceed without it.
.center
(figure CONTOUR near here)
.center
ε1The imaging process preserves points of inflexion in a planar curveε0
    The restrictions ε1R1-R3ε0 are very general, and guarantee
only the integrity of ε1cε0 and ε3gε0, not their interpretability.
Let us therefore suppose that a contour ε1cε0, like that shown in figure
CONTOUR, was obtained under conditions that satisfy the restrictions,
and ask what properties of ε1cε0 we can rely upon.  Clearly, no metric
properties of ε1cε0 can be used, because ε1cε0 arises from viewing a
surface ε3sε0 at an unknown orientation -- i.e. through at best a
linear operator, and such operators do not preserve metrics. The values
of ε1cε0's maxima and minima, and their separation, remain
uninformative until substantially more is known about ε3sε0 and the
perspective from which it is being viewed. But the qualitative notions
of maxima and minima on a curve ε1areε0 preserved by a linear operator
-- that is, the distinction between convex and concave is invariant.
This fact is captured by
.sp
.twinch 5.0
ε1Lemma 1.  Let ε1f(x, y)  =  0ε0 describe a planar curve that is
twice differentiable with continuous second derivative.  Let ε1L  :
Rε02↔ε1 ---->  Rε02↔ε0  be a non-singular linear transform of the
plane. Then ε1Lε0 preserves points of inflexion in ε1fε0.
.twinch 6.0
ε1Proof:ε0  We define ε1g  =  Lfε0,  the image of ε1fε0 under ε1Lε0,
by  ε1g(x, y)  =  f(Lε0-1↔ε1(x, y)).ε0  Since ε1Lε0 is linear and
non-singular, it induces a ε1(1 - 1)ε0 correspondence between the
slopes of tangents to ε1fε0 and tangents to ε1gε0.  We can represent
the set of possible slopes by the unit circle ε1Sε01↔ε0, and so
ε1Lε0 induces a map ε1Lε0*↔ε1 :  Sε01↔ε1  ---->  Sε01↔ε0, which is
ε1(1 - 1)ε0 and onto.  Hence ε1Lε0*↔ε0 is monotonic (either
increasing or decreasing) -- that is, if ε3q↓↓ε03↔ε0 lies between
ε3q↓↓ε01↔ε0 and ε3q↓↓ε02↔ε0, and |ε3q↓↓ε01↔ε0 - ε3q↓↓ε02↔ε0| < 2ε3pε0,
then ε1Lε0*↔ε1(ε3q↓↓ε03↔ε0) lies between ε1Lε0*↔ε1(ε3q↓↓ε01↔ε1)ε0
and ε1Lε0*↔ε1(ε3q↓↓ε02↔ε1)ε0. Now a point of inflexion ε1Xε0 on ε1fε0
is a stationary point for the slope of the tangents to ε1fε0.  Because ε1Lε0*↔ε0 is
monotonic, ε1L(X)ε0 is therefore a stationary point for the slope of
the tangents to ε1Lf = gε0. Hence ε1L(X)ε0 is an inflexion point on
ε1gε0.

    (I have used a geometric rather than an analytic argument
because it is clear how the same argument applies to the case where
ε1fε0 is piecewise linear. In this situation, the analog of an
inflexion point is a point where the sign of the change in gradient
reverses, and the argument used here still applies).
    Let us therefore suppose that we have been presented with a
contour segment like that shown in figure CONTOUR. Restriction ε1R3ε0
guarantees that adjacent points on the contour arise from adjacent
points on the surface ε3sε0, but no metrical features are yet
reliable. The only straightforward feature that remains is the
distinction between a convex contour segment and a concave one, which
rests in turn on the notion of an inflexion point.  For a general
surface ε3sε0 and contour generator ε3gε0, even points of inflexion
in ε1cε0 will often be meaningless, and to attribute significance to
them is to make an additional assumption about ε3sε0. So we next ask,
what exactly does this assumption entail?
    The restrictions ε1R1-R3ε0 allow us to think of ε3gε0, the
contour generator of ε1cε0 on ε3sε0, as a piece of wire bent in 3-space.
For distant viewing points, the imaging process can be approximated by a
linear transformation, which is the only kind that preserves a point of
inflexion. Inflexion points in ε1cε0 are however significant only if
the transformation that produced ε1cε0 was linear, and if the curve on
which that transform acted originally lay in a plane. In other words,
the convex-concave distinction can be meaningful in ε1cε0 only if the
bent wire that is ε3gε0 is planar. This gives us the fourth condition.
.br
  ε1Restriction R4:  The contour generator ε3gε1 of c is planar.ε0
.br
This condition is a strong one, and sharply delimits the class of
possible surfaces ε3sε0. There seems however to be no way of avoiding
it if one wishes to use the distinction between convex and concave
contour segments.
    We may demand that the restrictions ε1R2-R4ε0 hold for all
views, or for a subclass of the possible views of ε3sε0.  In either
case, the set ε1R1-R4ε0 delimits a certain class of surfaces, and this
class has a close relation to the assumption that the shape of a surface
may be inferred from its occluding contours. We now examine the nature
of this class of surfaces.
.block 4
.sp
.center
ε2Implications of the four restrictionsε0
    A ε1generalized coneε0, illustrated in figure GC, is the
surface swept out by moving a given cross-section ε3rε0 along some axis,
at the same time magnifying or contracting ε3rε0 in a smoothly varying
way. More formally, we make the
.twinch 5.0
.br
ε1Definitionε0. Let ε3rε1(ε3qε1)ε0 be a simple closed planar
curve that is twice continuously differentiable; and let ε1hε0 be a
twice continuously differentiable real function. Let ε3cε0 be a line
at some angle ε3yε0 to the plane of ε3rε0, and denote positions
along ε3cε0 by the variable ε1zε0. Let ε3sε0 be the surface
generated by the points ε1(h(z).ε3rε1(ε3qε1), ε3qε1, z)ε0. Then
ε3sε0 is a ε1generalized coneε0 with ε1axis ε3cε1, cross-section
ε3rε1, scaling function h,ε0 and ε1eccentricity ε3yε0. If ε3yε1
= ε3pε1/2ε0, ε3sε0 will be called a ε1right generalized coneε0.
.twinch 6.0
.center
(figure GC near here)
.br
ε11: The restrictions hold for all distant viewing points that lie in a
plane ε3pε0.
.br
.twinch 5.0
ε1Theorem 1.ε0 Let ε3sε0 be a generalized cone with convex
cross-section ε3rε0.  Then ε3sε0 satisfies
.br
ε1R1: ε3sε1 is everywhere twice differentiable with continuous second derivative,ε0
and for all distant viewing points that lie in a plane parallel to that
of the cross-section ε3rε0, it satisfies the conditions
.br
ε1R2: The inverse ε3iε0-1↔ε1 : ε1cε1 ----> ε3gε1 is one-valued.ε0
.br
ε1R3: The inverse ε3iε0-1↔ε1 : c ----> ε3gε1 is continuous.ε0
.br
ε1R4:  The contour generator ε3gε1 of c is planar.ε0
.br
Conversely, if ε1R1ε0 is satisfied by the simple close surface
ε3sε0, and if ε1R2 - R4ε0 are satisfied for all distant viewing
points that lie in some plane ε3pε0, then ε3sε0 is a generalized
cone with convex generating cross-section ε3rε0 that lies parallel to
ε3pε0.
.twinch 6.0
.br
ε1Proof:ε0  Our definition of a generalized cone ensures that it
satisfies ε1R1ε0.  Since ε3sε0 is generated by moving ε3rε0 along
the axis ε3cε0 (see figure GC), a given radial ε1PG  =
(ε3rε1(ε3qε1), ε3qε1)ε0 sweeps out a plane ε3lε0 containing ε3cε0,
as ε3rε0 itself is moved along ε3cε0. As ε3rε0 moves, the radial
ε1PGε0 maintains its direction, but shrinks or expands in a manner
dictated by the scaling function ε1h(z)ε0. As ε1Gε0 moves, it traces
out a curve on ε3sε0, which we shall call ε3gε0, and which lies in the
plane ε3lε0. Furthermore, the tangent to ε3sε0 at ε1Gε0 that lies
in the plane of ε3rε0 is the tangent ε1GVε0 to ε3rε0 at ε1Gε0,
for all positions of ε1Gε0. Suppose that we represent the direction of
ε1GVε0 in the plane of ε3rε0 by ε3fε0. If one views ε3sε0 from a
great distance in the direction ε3fε0, the line ε1GVε0 is a line of
sight to the edge of the surface ε3sε0. Therefore ε1Gε0 lies on the
contour generator of ε3sε0 for this view of ε3sε0. But this is true
for all positions of ε1PGε0 as ε1Pε0 moves along ε3cε0, and so ε3gε0
is a contour generator. Furthermore, since ε3rε0 is convex, the same
will be true for every angle ε3fε0 and corresponding point ε1Gε0 on
ε3rε0, provided that the viewing directions lie in the plane of
ε3rε0. Hence ε3sε0 satisfies ε1R2 - R4ε0 for all such distant
viewing positions.
    The proof of the converse result is longer, and we first need to
establish three lemmas.
.br
.twinch 5.0
.center
(figure L2 near here)
ε1Lemma 2.  ε3sε0 ∩ ε3pε0/↔ε0 is convex for all planes ε3pε0/↔ε0
parallel to the plane ε3pε0 of the given viewing angles.
.br
.twinch 6.0
ε1Proof:ε0  Suppose that   ε3sε0 ∩ ε3pε0/↔ε0  were not convex. Then
there would exist a line in  ε3pε0/↔ε0  that was tangential to  ε3sε0 ∩ ε3pε0/↔ε0
at two points ε1G↓↓ε01↔ε0 and ε1G↓↓ε02↔ε0 say, as shown in figure L2.
But the line ε1G↓↓ε01↔ε1G↓↓ε02↔ε0 is the ray that produces the edge of
the image of ε3sε0 from this viewing angle, and  ε1G↓↓ε01↔ε1G↓↓ε02↔ε0
therefore projects to a point ε1Vε0 say, on ε1cε0.  So
ε3iε0-1↔ε1(V)ε0  would contain both  ε1G↓↓ε01↔ε0 and ε1G↓↓ε02↔ε0, and
so would not be single-valued. This contradicts ε1R2ε0.
.sp
.twinch 5.0
ε1Lemma 3.ε0  If two distinct contour generators on ε3sε0 intersect
at a point ε1Xε0, then contour generators for all distant viewing
directions in the plane ε3pε0 pass through ε1Xε0.
.br
.twinch 6.0
ε1Proof:ε0  The tangent plane to ε3sε0 at ε1Xε0, which exists by
ε1R1ε0, contains two distinct vectors that lie in a plane parallel to
ε3pε0. Hence the tangent plane at ε1Xε0 must itself be parallel to ε3pε0.
.br
.center
(figure L4 near here)
.twinch 5.0
ε1Lemma 4.ε0  Let ε3g↓↓ε01↔ε0 and ε3g↓↓ε02↔ε0 be contour generators
for two different viewing directions in ε3pε0. Then  ε3g↓↓ε01↔ε0  and  ε3g↓↓ε02↔ε0 
intersect on ε3sε0.
.br
.twinch 6.0
ε1Proof. Since ε3sε0 is a simple closed surface,  ε3g↓↓ε01↔ε0 and ε3g↓↓ε02↔ε0 
each divide ε3sε0 into two connected components, each homeomorphic to
the unit disc.  Let   ε3pε0/↔ε0  be any plane parallel to ε3pε0 that
intersects ε3sε0 in more than a point.    ε3sε0 ∩ ε3pε0/↔ε0
is a simple closed convex curve, which meets  ε3g↓↓ε01↔ε0 in   ε1G↓↓ε01↔ε0
and  ε1G↓↓ε03↔ε0, and which meets   ε3g↓↓ε02↔ε0 in   ε1G↓↓ε02↔ε0 and
ε1G↓↓ε04↔ε0, as illustrated in figure L4.  The tangents to  ε3sε0 at   ε1G↓↓ε01↔ε0
and  ε1G↓↓ε03↔ε0  are parallel, and so are the tangents at  ε1G↓↓ε02↔ε0
and  ε1G↓↓ε04↔ε0. Clearly, the line  ε1G↓↓ε01↔ε0ε1G↓↓ε03↔ε0  divides the
simple closed curve   ε3sε0 ∩ ε3pε0/↔ε0  into two parts, in one of
which lies  ε1G↓↓ε02↔ε0, and in the other of which lies  ε1G↓↓ε04↔ε0. But
ε1G↓↓ε02↔ε0 and  ε1G↓↓ε04↔ε0 both lie on ε3g↓↓ε02↔ε0, whereas  ε1G↓↓ε01↔ε0
and  ε1G↓↓ε03↔ε0 both lie on ε3g↓↓ε01↔ε0.  Hence ε3g↓↓ε01↔ε0 and ε3g↓↓ε02↔ε0
must intersect somewhere on ε3sε0.
.br
ε1Corollary:ε0 ε3g↓↓ε01↔ε0  and ε3g↓↓ε02↔ε0 intersect twice or more.
.center
(figure T1 near here)
    We can now complete the proof of theorem 1.  Let ε3g↓↓ε01↔ε0  and ε3g↓↓ε02↔ε0
be two contour generators for ε3sε0 for different viewing directions
lying in ε3pε0. Since ε3g↓↓ε01↔ε0 and ε3g↓↓ε02↔ε0 are both planar (by
ε1R4ε0), their containing planes intersect in a line ε3cε0 (say). By
lemma 4, ε3g↓↓ε01↔ε0 and ε3g↓↓ε02↔ε0 intersect in at least two points,
and these points must therefore lie along the line ε3cε0. Let ε1Nε0
be a boundary point of the set of intersection points of ε3g↓↓ε01↔ε0  and ε3g↓↓ε02↔ε0
on ε3cε0, and let ε1Sε0 be the next closest such point to ε1Nε0.
This situation is depicted in figure T1. By lemma 2, all contour
generators pass through ε1Nε0 and ε1Sε0, which we may therefore
think of as north and south poles of ε3sε0, and therefore the planes of
all countour generators for views of ε3sε0 from ε3pε0 must contain
ε1Nε0 and ε1Sε0 and hence the line ε3cε0. That is, the planes of
all contour generators for distant views from the plane ε3pε0 will
intersect in ε3cε0.
    Let  ε3pε0/↔ε0 be a plane parallel to ε3pε0 lying between
ε1Nε0 and ε1Sε0, distant ε1zε0 from ε1Nε0, as shown in figure
T1a. Let ε3pε0/↔ε0 intersect ε3cε0 at ε1Hε0,  ε3g↓↓ε01↔ε0 at
ε1G↓↓ε01↔ε0, and ε3g↓↓ε02↔ε0 at  ε1G↓↓ε02↔ε0.
The configuration in ε3pε0/↔ε0
is shown in figure T1b. The crucial step in the proof is to notice that
up to scalar magnification,
the geometry of figure T1b is independent of ε1zε0, the position of ε3pε0/↔ε0
between ε1Nε0 and ε1Sε0. This follows from the following observations:
.br
(i) The angle between ε1Hε1G↓↓ε01↔ε0 and ε1Hε1G↓↓ε02↔ε0 is independent
of ε1zε0, because it is simply the angle between the planes of ε3g↓↓ε01↔ε0 and
ε3g↓↓ε02↔ε0 measured parallel to ε3pε0;
.br
(ii) The direction of the tangent to ε3rε0 at  ε1G↓↓ε01↔ε0 is
independent of ε1zε0, because as ε1zε0 increases,  ε1G↓↓ε01↔ε0
traces out the contour generator ε3g↓↓ε01↔ε0, which is by definition the
locus of tangents to ε3sε0 parallel to ε3pε0 for a given fixed
viewing direction ε3fε0.
    We deduce that for each angle ε3qε0 in figure T1b, the tangent
to the curve ε3rε0 has a constant direction for every ε1zε0. That
is, for each ε1zε0, the cross-sections ε3rε0 of ε3sε0 in ε3pε0/↔ε0
are all solutions of the ε1sameε0 equation
.nofill
.center
    ε1r.dε3qε1/dr  =  f(ε3fε1)                       (1)ε0
.adjust
.br
where ε1fε0 is some function of the viewing angle ε3fε0 and is
independent of ε1zε0. Let ε1R(ε3qε1)ε0 be a solution to ε1(1)ε0.
Then the cross-section function ε3rε0 of ε3sε0 has the form
.nofill
.center
    ε3rε1(qε1, z)  =  h(z).R(ε3qε1)                  (2)ε0
.adjust
.br
where ε1hε0 is a real function of ε1zε0.  Finally, ε3sε0 is twice
continuously differentiable, by ε1R1ε0.  Hence ε1hε0 is a twice
continuously differentiable function of ε1zε0, and so is ε1Rε0 of
ε3qε0. This completes the proof of theorem 1.
.br
ε1Corollary 1:  h  =  0  ε0 at ε1Nε0 and at ε1Sε0.
.br
ε1Corollary 2:ε0  The cross-section ε3rε0 can change at the poles
where ε1h  =  0ε0.
.sp
ε12.  The restrictions hold for distant viewing points in every directionε0
.br
.twinch 5.0
ε1Theorem 2.ε0 A necessary and sufficient condition
for ε3sε0 to satisfy ε1R1ε0, and
.br
ε1R2 - R4ε0 for all distant viewing positions, is that ε3sε0 be a quadratic surface.
.br
.twinch 6.0
ε1Proof:ε0  If ε3sε0 is a quadratic surface, it satisfies ε1R1 - R4ε0.
This follows from the following three observations:
.br
(i) A sphere trivially satisfies ε1R1 - R4ε0
.br
(ii) Any linear transformation preserves ε1R1 - R4ε0
.br
(iii) Any quadratic surface may be derived from a sphere by a linear
transformation. 
    Conversely, suppose that ε3sε0 satisfies ε1R1 - R4ε0 for all
viewing angles. Since the conditions of theorem 1 hold for every viewing
angle, ε3sε0 may be thought of as a generalized cone with generating
cross-sections in any direction. Hence, any two parallel planes
intersect ε3sε0 in curves that, if not null, have the same shape.
Suppose that ε3sε0 is the surface ε1f(x, y, z)  =  0ε0. Then a set
of such parallel planes is given by the family
ε1z  =  ax  +  by  +  cε0, for varying ε1cε0. We deduce that the curvesε1
	f(x, y, ax + by + c↓↓ε01↔ε1)  =  0
	f(x, y, ax + by + c↓↓ε02↔ε1)  =  0ε0
.br
are identical, up to magnification and a translation.  Hence the
ε1c↓↓ε0i↔ε0 cannot multiply terms of second or higher order. Therefore,
in the original equation, ε1zε0 cannot multiply terms of second or
higher order. Since the condition holds for arbitrary planes, it must
also be true of ε1xε0 and of ε1yε0, and it must hold identically.
Hence ε1fε0 is at most quadratic, and we have already seen that
quadratic surfaces satisfy the conditions of the theorem.
.sp
    Some intuition about the way in which theorem 2 fails for
higher-order surfaces may be gained by observing the behaviour of 
ε1xε02n↔ε1  +  yε02n↔ε1  +  zε02n↔ε1  =  1 ε0(see figure S-C).  This surface is a
sphere for  ε1n  =  1ε0, and tends to the unit cube as ε1nε0 grows large.
The contour generator ε3gε0, which is a circle for ε1n = 1ε0 (figure S-Ca),
becomes the outline marked with thick lines in figure S-Cb for high
values of ε1nε0. This contour-generator is clearly not planar; the
lower third is pulled towards the viewer as ε1nε0 increases, and the
upper third is pushed away.
.center
(figure S-C near here)
.sp
.block 4
.center
ε1Remarks about theorems 1 and 2 and their proofsε0
    The premises of these theorems, and the way the premises are used in
the proofs, seem generally reasonable with one possible exception. That
is the use of ε1R2ε0 to show that
.br
ε3sε0 ∩ ε3pε0/↔ε0 is convex in
lemma 2. In fact, this is how ε1R2ε0 forces the cross-section of
ε3sε0 to be convex, which is a condition that holds all through these
results. One might argue that this is a somewhat artificial use of
ε1R2ε0, which was introduced mainly to exclude surfaces that contain
lines. The analysis given so far concerns only the silhouette of the
image of ε3sε0 however, and in these circumstances the convexity
assumption for ε3rε0 is a reasonable one, because violations cannot be
detected from viewing directions that lie parallel to the plane of
ε3rε0. In practise, one can apply the above analysis to all occluding
contours in an image, provided that one subsequently relates the
different cylinder descriptions that emerge for different parts of the
same surface. Figure SPIKE (see below) shows a simple example of this.
    If one accepts the validity of the restrictions ε1R1 - R4ε0,
the meaning of these theorems is clear. They essentially state that, the
assumption that a surface's shape can successfully be inferred from only
its bounding contours in an image, is equivalent to an ε1a prioriε0
assumption that the viewed shapes are generalized cones, or are composed
of them. In practise, one also has available additional information from
the subtler cues of shading, texture gradients, motion and binocular
disparity; but other, different assumptions probably underlie the
interpretation of these other types of information.
    These results provide a further argument for using something
based on generalized cylinders (Binford 1971) for the internal
representation of shape (see Marr & Nishihara 1976), an argument based
not on utility, as most other justifications are, but on the assumptions
implicit in the decoding of an image. It is indeed extremely fortunate
that many important three-dimensional structures can be closely
approximated by a few generalized cones, although it is not accidental
that objects whose shape was achieved by growth like limbs and
stalagmites, can be so approximated.
.sp
.center
ε2Interpreting the image of a single generalized coneε0
    Theorem 1 shows us that, in relying upon the distinction between convex
and concave contour segments, we are effectively assuming that the
viewed shape is composed of generalized cones. In the second half of
this article, we therefore study how this assumption helps the
interpretation of an image. We shall assume that the viewed shape is
constructed of generalized cones, and we ask how occluding contours in
the image may be used to find their axes. This section is concerned with
the image of a single generalized cone. We first assume that the
conditions of theorem 1 hold, and ask how the cone's axis may be
recovered from the image. Then we examine the stability of this result
as its prerequisites are violated in four common ways; (i) the viewing
directions are not coplanar with the generating cross-sections of the
cone, (ii) the cross-section of the cone is not convex, (iii) the cone
is viewed from a nearby rather than from a distant point, and (iv) the
axis of the cone is not a straight line.
.sp
.center
(figure T3 near here)
.block 4
.center
ε1Finding the axis from a favourable viewε0
    Provided that the viewed surface is a generalized cone, and that
the viewing point satisfies the conditions of theorem 1, the axis of the
cone may easily be determined.
.twinch 5.0
ε1Theorem 3 (Axial Symmetry).ε0  Let ε3sε0 = ε3rε0 x ε1hε0 be a
generalized cone with convex cross-section ε3rε0, viewed distantly
from its associated viewing plane ε3pε0, and let the cross-section
scaling function ε1h(z)ε0 contain at least one concavity. Then
.br
(i) the silhouette of ε3sε0 decomposes into ε1n > 2ε0 contour
segments by splitting it at points of inflexion;
.br
(ii) the image of the axis ε3cε0 of ε3sε0 establishes an axial symmetry
between at least ε12ε0 or ε1(n - 2)ε0 (whichever is greater) contour
segments, including all concave segments, such that segments that
correspond under the symmetry are either both convex or both concave;
.br
(iii) if ε1c↓↓ε0i1↔ε0 and ε1c↓↓ε0i2↔ε0 are corresponding segments, and
if ε1d(c↓↓ε0i↔ε1)ε0 denotes the average perpendicular distance from
ε1c↓↓ε0i↔ε0 to the image of the axis, then ε1d(c↓↓ε0i1↔ε1)/d(c↓↓ε0i2↔ε1)ε0 
is independent of ε1iε0.
.twinch 6.0
.br
ε1Proof:ε0  Since ε3sε0 is a generalized cone and ε3rε0 is convex,
the contour generators for its image are the curves
ε1(h(z).ε3rε1(ε3q↓↓ε01↔ε1), ε3qε0↓↓1↔ε1, z)ε0 and
ε1(h(z).ε3rε1(ε3q↓↓ε02↔ε1), ε3qε0↓↓2↔ε1, z)ε0
for fixed ε3q↓↓ε01↔ε0 and ε3q↓↓ε02↔ε0
and variable ε1zε0, as shown in figure T3.  Hence as ε1h(z)ε0
increases, the distance from contour generator to the image ε3cε0*↔ε0
of the axis ε3cε0 increases on both sides of ε3cε0*↔ε0. Hence if ε1h(z)ε0
has a concave portion, it will generate two concave segments ε1c↓↓ε01↔ε0
and ε1c↓↓ε02↔ε0 in ε1cε0, one either side of ε3cε0*↔ε0 and
symmetrical about ε3cε0*↔ε0 (with a possible lateral displacement
unless ε3sε0 is a right generalized cone).  Also, ε1d(c↓↓ε01↔ε1)/d(c↓↓ε02↔ε1)
ε0depends upon the value of ε3rε1(ε3q↓↓ε01↔ε1)/ε3rε1(ε3q↓↓ε02↔ε1), ε0and
not on the particular choice of contour segment (i.e. of ε1zε0).
  These remarks hold for all convex and concave segments of ε1hε0,
except possibly for those at each end of ε3sε0 (see figure T3). In
figure T3, there is effectively only one end segment, namely
ε1c↓↓ε03↔ε0, but in general there may be 2. Hence the symmetry
established by the axis ε3cε0*↔ε0 holds for at least ε1(n - 2)ε0 of
ε1cε0's contour segments, (or 2 of them if ε1n = 3ε0), and it matches
up all contour segments that are concave, since the end segments must be
convex. Finally, there must be at least three contour segments, since
the premises of the theorem require that there be 2, and ε1cε0 is a simple
closed curve.
.br
ε1Corollary:ε0 The image of the axis of ε3sε0 is uniquely determined
if there exists only one such axial symmetry.

.twinch 5.0
ε1Definition.ε0  The type of symmetry established by
theorem 3, which holds between convex or concave segments of a
contour and which includes a scaling factor, we shall call a
ε1qualitative symmetryε0.

.twinch 6.0
    Although there is a point-wise symmetry between the contour on
the two sides of the axis, unless the viewed surface is a right
generalized cone and the contours are faithfully diagnosed in the image,
such symmetries are difficult to find. The importance of the theorem is
that a qualitative symmetry does not have to be found on a point-by-point basis.
By dividing the contour into convex and concave segments and noticing that the symmetry
preserves this distinction, we have reduced the number of items involved
in it to a small one. Hence the problem of ε1findingε0 the symmetry
(and hence its axis) becomes computationally feasible. Further, the
corollary to theorem 3 ensures that if there is only one qualitative symmetry
in the image, the axis of ε3sε0 is uniquely determined.
This fact has a practical importance,
since it allows one to place confidence in the results delivered by the
analysis of contour at this level without having to appeal to some kind
of consistency in their subsequent interpretation.

.center
(figure SPIKE near here)
.center
ε1Viewing directions not coplanar with ε3rε0
    We next ask what happens to the generalized cones of theorem 3
if the viewpoint remains distant, but if the viewing direction moves out
of its constraining plane ε3pε0. As we have seen, while the viewing
direction lies in ε3pε0, variations in the silhouette of ε3sε0 are
due to changes in ε1h(z)ε0 along the cone's axis ε3cε0, as
illustrated by figure SPIKEa. When the viewpoint is moved so drastically
that the viewing direction lies parallel to ε3cε0, the silhouette of
ε3sε0 is due entirely to ε3rε0, its cross-section, and is in fact
due to the cross-section of ε3sε0 at the point where ε1h(z)ε0
achieves its maximum value (giving an image like that shown in figure SPIKEb).
    At both of these extremes the contour generator on ε3sε0 is
planar, but for other viewing directions it need not be. This is true
even for a surface as simple as an egg, where the contour generator is a
circle for the end-view, an oval for a side view, and slides from one to
the other in between (see figure EGG-SKEL below).
The effect on inferences about an egg's shape of
maintaining the assumption that the contour generator is planar even for
these intermediate views is to attribute a given change in curvature to
a shorter distance than that over which it in fact occurs.
    This effect can easily produce small quantitative errors in the
description of a shape, for which it is difficult to compensate without
additional information. But such errors rarely play a significant role
in the type of analysis to which theorem 3 leads. The important question
for the qualitative analysis of shape that we are pursuing is how often
is the convex/concave distinction in a contour genuinely misleading?
    The case of the egg differs from that of the surface depicted in
figure SPIKE in that as the egg rotates, there is only ever one
occluding contour, namely the egg's silhouette. As the surface in figure
SPIKE rotates however, occluding contours can arise from the silhouette
and from the cross-section (see for example figure SPIKEc). This happens
because an egg is convex, whereas the surface in figure SPIKE is not.

.twinch 5.0
ε1Lemma 5.ε0 If ε1hε0 and ε3rε0 are both convex, and ε3sε1 = h
ε0x ε3rε0, then every orthogonal projection of ε3sε0 is convex, and
the only occluding contours in the image of ε3sε0 are those in its silhouette.

.twinch 6.0
Hence if ε3sε0 is convex, its image consists of a simple closed curve,
and we can deduce nothing further in general unless extra information is
available, for example from shading or stereopsis.
    If ε3sε0 is not convex and ε3rε0 is (which is an assumption
of this section), the analysis of ε3sε0 can proceed somewhat further.
Like the egg, the contour generators on ε3sε0 are not necessarily
planar except for views taken parallel to the axis ε3cε0 or to the
plane of ε3rε0. Unlike the egg however, we can make an approximation
to the contour generators that is tolerably accurate for most viewing
angles, and hence of considerable practical usefulness. The
approximation is based on the same idea as the approximation given above
for the egg's outline. In figure SPIKE, the contour generator on ε3sε0
consists of two components, one due to ε1hε0 along the "sides" of
ε3sε0, and one due to ε3rε0 that roughly follows the cross-section
of greatest diameter. If ε3sε0 is smooth, the true contour generator
will not follow the greatest cross-section exactly, nor will the part
that runs down the "sides" of ε3sε0 be exactly coplanar, but for most
distant viewpoints these conditions will be roughly satisfied.
.center
(figure ODDVIEW near here)
    This idea may be generalized in the following way. Let ε3sε0
be a generalized cone, and suppose that it is being viewed from a
distant point ε1Vε0. Let ε1Vε3sε0 make an angle ε3aε0 with the
plane ε3pε0 parallel to the cross-section ε3rε0 of ε3sε0 (see
figure ODDVIEW) and let the projection ε1Vε0/↔ε3sε0 of ε1Vε3sε0 in
ε3pε0 correspond to a viewing angle of ε3fε0 in ε3pε0. Let
ε1cε0/↔ε0 denote the silhouette of ε3sε0 as viewed from ε1Vε0/↔ε0,
and let ε3gε0/↔ε0 denote the contour generator of ε1cε0/↔ε0. Then
those portions of the contour generator ε3gε0 for viewpoint ε1Vε0 that
run along the "sides" of ε3sε0 are approximated, where visible, by
ε3gε0/↔ε0. The remainder of ε3gε0 is approximated by
parts of the maximal cross-sections
of ε3sε0, which we shall denote by ε3hε0. The whole of ε3gε0
is thus approximated by combining ε3gε0/↔ε0 and ε3hε0. More formally,
.sp
.twinch 5.0
ε1Definition.ε0 The set ε3hε0 of points ε1h(z↓↓ε0i↔ε1).ε3rε1(ε3qε1)ε0
for all ε3qε0 and each value of ε1z↓↓ε0i↔ε0 that makes ε1h(z↓↓ε0i↔ε1)ε0 a local
maximum or minimum, is called the ε1radial extremityε0 of ε3sε0. The set
.br
ε3gε0/↔ε0 ∪ ε3hε0 is called the ε1skeletonε0 of ε3sε0 for the
viewing point ε1Vε0.

.center
(figure SKELETONS (which includes EGG-SKEL) near here)
.twinch 6.0
The skeleton of a surface, as defined in this way, is a natural concept
and is illustrated in figure SKELETONS. The idea is that the image of
a skeleton approximates the contours that appear in an object's image.
For example, in the case of an egg of length ε1lε0 and diameter
ε1dε0, the skeleton (shown in figure EGG-SKEL) has length ε1l.sin(ε3qε1)ε0
and width ε1dε0, when viewed in a plane containing the egg's major
axis at an angle ε3qε0 to it.  For angles where ε1l.sin(ε3qε1) > dε0,
this is a reasonable approximation, and for other values of
ε3qε0, we use the diameter ε1dε0.
    The reason why the skeleton is a
useful construct for recognition is that one can detect its presence
in an image by the many relationships that exist among
its parts. In fact, we can use these relationships to set up constraints
on a set of occluding contours such that if those constraints are all
satisfied by a unique interpretation of the contours in the image, we
can be reasonably certain that we have found a skeleton, and hence can
interpret the contours as arising from a generalized cone ε3sε0 whose
axis is then determined. These comments are made precise by

.twinch 5.0
ε1Theorem 4 (Skeleton Theorem).ε0 Let  ε3gε0/↔ε0 ∪ ε3hε0 be the
skeleton of ε3sε0 associated with some viewing point ε1Vε0. Then
.br
(i) ε3gε0/↔ε0 is qualitatively symmetric about the image of the axis ε3cε0 of
ε3sε0, in the sense of theorem 3
.br
(ii) ε3hε0 consists of one or more connected components, through which
ε3cε0 passes, and between any two components of which there exists a
mapping that is ε1(1 - 1)ε0, continuous and onto, that preserves the
gradient of ε3hε0 at each point.
.twinch 6.0
ε1Proof:ε0  Since ε3gε0/↔ε0 correponds to a viewing direction that
is coplanar with the cross-section ε3rε0, it obeys the conditions of
theorem 3, and the image of the axis ε3cε0 induces a qualitative symmetry between
its concave and convex components. Secondly, ε3hε0 trivially consists
of one or more connected components through which ε3cε0 passes, since
these components are just cross-sections at the local maxima and minima of ε1hε0.
Finally, if ε1h(z↓↓ε01↔ε1)ε0 and ε1h(z↓↓ε02↔ε1)ε0 are local maxima
or minima of ε1hε0, the mapping between points on ε3sε0 given by
     ε1(h(z↓↓ε01↔ε1).ε3rε1(ε3qε1), ε3qε1, z↓↓ε01↔ε1)  ---->   (h(z↓↓ε02↔ε1).ε3rε1(ε3qε1), ε3qε1, z↓↓ε02↔ε1)
.br
ε0is continuous, ε1(1 - 1)ε0, onto, and preserves the gradient of
ε3hε0 at each point, since the gradient of both at ε3qε0 is
ε3rε1.dε3rε1/dε3qε0.
.br
ε1Corollary:ε0 If ε3sε0 obeys the prerequisites of theorem 4, and if
its skeleton decomposes in a unique way into two parts ε3gε0/↔ε0 and
ε3hε0 that satisfy conditions (i) and (ii) of the theorem, then the
components of ε3hε0 correspond to cross-sections of ε3sε0, and the
axis of symmetry is the image of the axis ε3cε0 of ε3sε0.

    As in the case of theorem 3, the diagnostic power of this result
lies in the corollary. It does not guarantee that a given set of
occluding contours can be interpreted, but if a unique interpretation
exists that satisfies these conditions, then it will be
correct. In practise this result is a useful
one. For example, it solves the image of a bucket shown in figure
BUCKET; the sides of the bucket are qualitatively symmetrical about its axis, and a
parallel relationship holds between the image of its top and the visible
part of its base. In a real image, many parts of the skeleton will be
obscured, but this hampers the finding of relationships like parallelism
and qualitative symmetry only slightly. One can devise a cooperative
algorithm (Marr & Poggio 1976) that can operate on the description of a
contour to find relationships of this kind between its pieces (Vatan &
Marr 1976).

.center
(figure BUCKET near here)
.center
ε1Generalized cones whose cross-section is not convexε0
    The important difference between this and the case where ε3rε0
is convex is that occluding contours can now arise from local maxima and
minima in ε3rε0 as well as from the silhouette due to ε1hε0 and
cross-sections at points where ε1h(z)ε0 achieves a local maximum or minimum. For
example, in the image of a fluted pillar, there are usually many lines
running parallel to the axis of the pillar corresponding to the local
maxima or minima in the pillar's cross-section. (In practise, one of the principal
difficulties in the analysis of such an image is to assign the labels
convex and concave to such internal lines correctly. This is the analog
in distance away from the viewer of convexities and concavities in an
object's silhouette.)
    In theory, the analysis of the more complex surfaces allowed by
adding concavities to ε3rε0 can proceed along the lines of theorem 4.
We need only add to the skeleton those contours that are due to
convexities and concavities in ε3rε0, and note that the convexities
and concavities in each such line will follow those of one half of
ε3gε0/↔ε0, the silhouette of ε3sε0. As ε3rε0 increases in
complexity however, the technical problems that arise in the surface's
interpretation increase in magnitude; obscuration becomes more and more
common, the important contours can become difficult to detect in the
image, and there is an increasing chance that at least some of those
that can be detected will fail to approximate the locus of ε3sε0's
skeleton with reasonable accuracy. I nevertheless state the relevant
theorem and corollary for the general case here, with a caution that, in
circumstances such as these that can become extremely complex, one often
cannot rely on contour information alone to analyse the surface.

.twinch 5.0
ε1Definition.ε0  Let ε3sε0 be a generalized cone,
and let ε3xε0 be the set of points ε1(h(z).ε3rε1(ε3q↓↓ε0i↔ε1), ε3qε0↓↓i↔ε1, z)
ε0for all ε1zε0, for each ε3q↓↓ε0i↔ε0
that makes ε3rε0 a local maximum or minimum. Then ε3xε0 is called
the ε1flutingε0 of ε3sε0. For a viewpoint ε1Vε0, let ε3gε0/↔ε0 ∪
ε3hε0 be the skeleton of ε3sε0 that occurs in theorem 4. We define
the ε1complete skeletonε0 by adding the fluting to ε3sε0's skeleton,
i.e. the complete skeleton of ε3sε0 from viewpoint ε1Vε0 is the set
ε3gε0/↔ε0 ∪ ε3hε0 ∪ ε3xε0.
.center
(figure FLUTING near here)

ε1Theorem 5.ε0  Let ε3gε0/↔ε0 ∪ ε3hε0 ∪ ε3xε0 be the complete
skeleton of ε3sε0 associated with some viewing point ε1Vε0. Then
.br
(i) ε3gε0/↔ε0 is qualitatively symmetric about the image of the axis ε3cε0 of
ε3sε0, in the sense of theorem 3
.br
(ii) ε3hε0 consists of one or more connected components, through which
ε3cε0 passes, and between any two components of which there exists a
mapping that is ε1(1 - 1)ε0, continuous and onto, that preserves the
gradient of ε3hε0 at each point.
.br
(iii) Each portion ε1(h(z).ε3rε1(ε3q↓↓ε0i↔ε1), ε3qε0↓↓i↔ε1, z)ε0
(for fixed ε3q↓↓ε0i↔ε0
and varying ε1zε0) of the fluting of ε3sε0 is either a straight
line, or it divides into convex and
concave segments that are in ε1(1 - 1)ε0 correspondence with the
convexities and concavities in that part of ε3gε0/↔ε0 that lies on one
side of its axis of symmetry.
.twinch 6.0
ε1Proof:ε0  Parts (i) and (ii) follow in the same way as theorem 4.
Part (iii) follows because like the two
qualitatively symmetric components of ε3gε0/↔ε0,
each contour in the fluting of ε3sε0 is generated by variations in ε1h(z)ε0.
If such a contour lies directly on the line of sight to the axis ε3cε0
of ε3sε0, it will appear in the image as a straight line. Otherwise,
its concavities and convexities will follow those of one component of ε3gε0/↔ε0,
although the depth of the concavities or convexities will differ in general.
.br
ε1Corollary:ε0 If ε3sε0 is a generalized cone, and if its complete
skeleton decomposes in a unique way into three parts ε3gε0/↔ε0,
ε3hε0 and ε3xε0 that satisfy conditions (i), (ii) and (iii) of
theorem 5 respectively, then the axis of symmetry of ε3gε0/↔ε0 is the
image of the axis of symmetry of ε3sε0, ε3hε0 are the radial
extremities of ε3sε0, and ε3xε0 is its fluting.

    Once again this result enables us to set up a system of
constraints on the contour present in an image such that, if the
constraints are satisfied by a particular labelling of the contour, that
labelling enables us to discover the axis ε3cε0 of ε3sε0, and other
information about its cross-section ε3rε0 and scaling function ε1hε0.
The algorithms that implement this method need only to recognise the
properties of parallelism and qualitative symmetry between a small number
of elements. This result reaches slightly beyond the scope of this article
since it deals with contour that is not necessarily occluding. It also
extends naturally to the case where ε3rε0 contains creases (points of
discontinuity in gradient). Creases often give rise to edges and highlights
in an image.

.center
(figures SNAKE and CURVED-AXES near here)
.center
ε1Nearby viewing points and curved axesε0
    The methods discussed in this article are ill-suited to images
that arise from nearby viewing points, and are of little use for cones
with curved axes unless their cross-sections are simple. These points
are best made by figure SNAKE, which shows a serpent weaving towards and
away from a nearby viewer (figure SNAKEa), who sees an image that
resembles figure SNAKEb. Here, the convex-concave distinction requires
an interpretation based on the varying distance to the viewer -- an
interpretation that must rely on other cues, like texture gradients and
stereopsis, for its main support.
    If one sees the contour that appears in figure SNAKEa, one can
and does infer the shape of a snake. Cases such as this, where the
scaling function ε1hε0 is roughly constant, are easy to deal with; so
are other cases where the qualitative symmetry of theorem 3 is reversed (i.e. convex
segments match concave segments as in figure CURVED-AXES, not convex
ones), but in general the situation is
complex. I have been unable to derive any substantial results from
circumstances in which the surface ε3sε0 and its viewing point are
unconstrained. If the axial curvature is slight, or if the cross-section
and axial scaling functions are particularly simple, special-purpose
results can be obtained. But if not, arbitrarily complex situations can
arise.

.center
ε2Surfaces composed of two or more generalized conesε0
    We have hitherto been concerned with the appearance of a single
generalized cone. Real-life objects are often approximately composed of
several different cones, joined together in various ways (see Marr &
Nishihara 1976 figure 6). The way in which two cones join has a profound but
usually local effect on the contours produced by the resulting surface,
and it can upset the qualitative symmetry and parallelism on which our
earlier results depended by interfering with the inflexion points on
which primary contour description is based. Therefore, the algorithms
for interpreting occluding contours in an image must incorporate a
sensitivity to situations that can arise as a result of joins.
    In this section, we study the common types of cone-cone
junction, classify the appearances to which they can give rise, and show
how algorithms for their detection may be constructed. In order to do
this, we once again have to place some restriction on the way in which a
join is configured. The one that we choose is
  ε1Restriction 5:  The axes of two joined generalized cones are coplanar.ε0
.br
The reason for requiring this is that it enables one to relate the
silhouette of the junction between two cones to the angle between their
axes and their axial scaling functions. If the two axes are not
coplanar, the surfaces at the junction are rather unconstrained.  In
practise, ε1R5ε0 is not a severe restriction. Provided that the two
axes approach one another closely relative to the width of their
respective cones, the coplanar condition will be satisfied closely
enough.

.center
ε1A: Side-to-end joins between two generalized conesε0
    The most useful common feature of the join between two cones is
that it gives rise to one, or a pair, of deep concavities in the surface's
silhouette. As we shall see, however, this feature is not a necessary
concomitant of a cone-cone junction, and although it plays a large
part in our algorithms for detecting such a junction, its role in the
underlying theory is surprisingly slight.
    It is convenient to divide the types of join that can occur
into two classes, those in which the end of one cone is attached to the
side of the other, and those in which the two cones are attached at
their ends. A formal statement of the distinction between these is
provided by the

.twinch 5.0
ε1Definition.ε0  For ε1 i = 1, 2ε0 let ε3s↓↓ε0i↔ be a generalized
cone with maximum width ε12w↓↓ε0i↔ and axis ε3cε0↓↓i↔ of length
ε1lε0↓↓i↔. Let ε3sε0↓↓1↔ and ε3sε0↓↓2↔ be joined, and let
ε3wε0 be the angle between their axes (see figure SIMPLE-JOIN). Then
the join between the cones will be called ε1side-to-endε0 (the side of
ε3sε0↓↓1↔ to the end of ε3sε0↓↓2↔) provided that
.br
(i) the two axes intersect between the ends of ε3cε0↓↓1↔
.br
(ii) the whole of the joined end ε1ABε0 of ε3sε0↓↓2↔ lies between the
two lines perpendicular to and passing through the ends of ε3cε0↓↓1↔ 
.br
(iii) one of the points ε1Aε0 and ε1Bε0 of figure SIMPLE-JOIN
does not lie within the convex hull of ε3sε0↓↓1↔.
.br
The join is called ε1end-to-endε0 if
.br
(i) the two nearest ends of ε3cε0↓↓1↔ and ε3cε0↓↓2↔ are within
ε1min (w↓↓1↔, w↓↓2↔)ε0 of one another, and
.br
(ii) the two furthest ends are
greater than ε1(w↓↓1↔ + w↓↓2↔)ε0 apart.

.twinch 6.0
The important difference between the two cases is that there have to be
two concavities associated with a side-end join, one on each side of
ε3cε0↓↓2↔ as shown in figure SIMPLE-JOINa, but there need not be for
end-to-end joins (figure SIMPLE-JOINb). These two types of join do not
cover all possible cases, but they cover most of them. To avoid unnecessary
detail, the remaining cases are not dealt with here, although they are
included in the discussion of algorithms that detect joins (Vatan & Marr
1976).
.center
(figures SIMPLE-JOIN and T6 near here)

ε1A1: Both cones are convexε0
    In its simplest form, the existence of the concavities that are
associated with the junction between two cones is established by 

.twinch 5.0
ε1Theorem 6.ε0  Let ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 be two convex generalized
cones such that the end of ε3s↓↓ε02↔ε0 joins the side of ε3s↓↓ε01↔ε0,
and the join satisfies restriction ε1R5ε0.  Let the lengths
of the cones' axes ε3c↓↓ε0i↔ε0 be ε1l↓↓ε0i↔ε0, and let the diameters of their
cross-sections be bounded by ε12w↓↓ε0i↔ε1 (i = 1, 2).ε0  Then 
.br
(i) the only concavities that can occur in the image are due to the junction
.br
(ii) viewed distantly perpendicular to the plane of ε3c↓↓ε01↔ε0 and
ε3c↓↓ε02↔ε0, the total concave angle present in the image is near
ε1180ε0o↔ε0 (in the sense made precise in the proof) provided that the
site of the join is not near an end of ε3s↓↓ε01↔ε0, and that ε3s↓↓ε01↔ε0
and ε3s↓↓ε02↔ε0 are much longer than they are wide.
.twinch 6.0
ε1Proof:ε0  By lemma 5, all contours derived separately from ε3s↓↓ε01↔ε0
and ε3s↓↓ε02↔ε0 are convex. Hence any concavity in the image of their
union must be due to the way they are joined. If ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0
have coplanar axes and are viewed perpendicularly to this plane, the
resulting configuration is as represented in figure SIMPLE-JOIN. The
contours shown in thick lines there represent cylinders ε1l↓↓ε0i↔ε0 long
and ε1w↓↓ε0i↔ε0 thick which, by the conditions of the theorem, bound the
cones ε3s↓↓ε0i↔ε1 (i = 1, 2).ε0  Let ε1Pε0 be one of the two points
at which contours due to ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 intersect, and let
ε1PQ↓↓ε01↔ε0 and ε1PQ↓↓ε02↔ε0 be the tangents to ε3s↓↓ε01↔ε0 and
ε3s↓↓ε02↔ε0 at ε1Pε0. Let ε3wε0 be the angle between the axes ε3c↓↓ε01↔ε0
and ε3c↓↓ε02↔ε0 of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0, and let ε3y↓↓ε01↔ε0 and
ε3y↓↓ε02↔ε0 be the angles that ε1PQ↓↓ε01↔ε0 and ε1PQ↓↓ε02↔ε0 make with
ε3c↓↓ε01↔ε0 and ε3c↓↓ε02↔ε0. Then the angle between ε1PQ↓↓ε01↔ε0
and ε1PQ↓↓ε02↔ε0 is ε1(180ε0o↔ε1 - ε3wε1 - ε3y↓↓ε01↔ε1 -
ε3y↓↓ε02↔ε1)  =  ε3aε0 (say).  The corresponding angle at the other
intersection ε1Pε0/↔ε0 between contours of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0
is ε1(ε3wε1 - ε3y↓↓ε03↔ε1 - ε3y↓↓ε04↔ε1) = ε3aε0/↔ε0 (say), as
illustrated in figure SIMPLE-JOIN. Hence the total concavity due to the join is
ε3aε1 + ε3aε0/↔ε1  =  (180ε0o↔ε1 - ε3y↓↓ε01↔ε1 - ε3y↓↓ε02↔ε1 - ε3y↓↓ε03↔ε1 - ε3y↓↓ε04↔ε1).
ε0In order to establish a lower bound for the total concavity, we need
to find upper bounds for the angles ε3y↓↓ε0i↔ε1 (i = 1 ε0toε1 4)ε0, and
we can use the convexity of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 to do this.
Since the scaling functions of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 are convex,
the maximum possible value of ε3y↓↓ε02↔ε0 is ε3f↓↓ε02↔ε0 (shown in
figure SIMPLE-JOIN), which is exactly
ε1tanε0-1↔ε1(w↓↓ε02↔ε1/2(l↓↓ε02↔ε1 - w↓↓ε02↔ε1.cot(ε3wε1)),ε0
and approximately ε1tanε0-1↔ε1(w↓↓ε02↔ε1/l↓↓ε02↔ε1)ε0.
The maximum possible value of ε3y↓↓ε01↔ε0 is ε3f↓↓ε01↔ε0, which is
approximately ε1tanε0-1↔ε1(w↓↓ε01↔ε1/d↓↓ε01↔ε1)ε0 (see figure SIMPLE-JOIN),
These approximations hold provided that the cones are long relative to
their widths, and ε1d↓↓ε01↔ε0 is not near 0 or ε1l↓↓ε01↔ε0 -- i.e. the join
is not near either end of ε3s↓↓ε01↔ε0.

    This straightforward result shows how points of concavity arise
at the junction of two convex cones, and it therefore gives us a method
for detecting such joins. Since angles of ε1180ε0o↔ε0 are preserved by
linear transformations, the effect of altering the viewing angle is
entirely due to changes in the angles ε3f↓↓ε0i↔ε0 that are caused by
foreshortening ε1l↓↓ε01↔ε0 or ε1l↓↓ε02↔ε0. This means that the join will
remain detectable until the projection of one cone's length becomes
comparable with the projection of its width, or until the junction is
obscured.
.block 4
.br
ε1A2: Cones not everywhere convexε0
    If the generalized cones ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 are not
convex -- for example, if their axial scaling functions contain concave
segments -- the concavities that "ought" to arise at their junction can
be concealed, appearing as part of the concavities due to their axial
scaling functions. The simplest case of this is shown by figure CONCEALED,
where there is no identifiable concavity due to the join. Our problem
here is therefore to classify the kinds of junctions that can occur, and
to show which kinds are usually detectable from a contour, and which are
not. We shall assume that ε1R5ε0 holds throughout this section.
    Suppose that an end of ε3s↓↓ε02↔ε0 joins the side of ε3s↓↓ε01↔ε0,
and that the resulting surface is viewed along the direction perpendicular
to the planes of the axes.  Figure PROFILES contains two examples of profiles that
can occur in this situation.
.center
(figures CONCEALED, PROFILES and SQUASHED-PROFILES near here)
    From the results obtained earlier, we can separate ε3s↓↓ε02↔ε0 into portions
in which ε1h↓↓ε02↔ε0 is convex, and those in which it is concave.   This cannot be
done if the angle ε3wε0 (figure SIMPLE-JOIN) between the two axes is very small,
since this can cause situations like that in figure SQUASHED-PROFILES
and even if ε3wε0 is large, the situation in
figure SQUASHED-PROFILES will arise for viewing angles that lie near the plane
containing the axes of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0.  In practise,
the profile of figure SQUASHED-PROFILESc
admits of an alternative decomposition, shown in SQUASHED-PROFILESd, and this is the
one that would be found by methods based on this theory.
     If ε3wε0 is sufficiently large, for viewing angles that do not lie
near the plane of the two axes ε3c↓↓ε01↔ε0 and ε3c↓↓ε02↔ε0,
ε3s↓↓ε02↔ε0 may be decomposed into
sectors at inflexion points of ε1h↓↓ε02↔ε0.  Those sectors distal to sectors
involved in the join are uninfluenced by the join, and will obey the
symmetry theorem 3.  Hence if such sectors belong exactly to one axial
symmetry such that the axis lies within the image of the surface,
the axis of that symmetry is the axis of ε3s↓↓ε02↔ε0.  Similar
remarks hold for sectors of ε3s↓↓ε01↔ε0 that are not involved in the join
between ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0.  Once partial axes have been found in this
way, the axes or axis fragments can be continued until the axis fragments of
ε3s↓↓ε01↔ε0 meet, and until the axes of ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 meet
(shown dotted in Figure LONG-AXES).
.br
.center
(figure LONG-AXES near here)
    This diagnostic technique relies on the existence of segments
distal to the junction, so we now deal with the case in which there are
none. If we assume that the join takes place entirely within one segment
of ε3s↓↓ε02↔ε0, there are six possible situations and they appear in
the top and bottom rows of Figure SIDENDJNS.  Four arise when
ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0  consist
of just one segment each, and it may be either convex or concave; the
other two arise because ε3s↓↓ε02↔ε0 can straddle a segment boundary in ε3s↓↓ε01↔ε0 (column
3 of Figure SIDENDJNS).  It is convenient to subdivide the cases where ε3s↓↓ε02↔ε0 is
concave into those cases in which the value of ε1h↓↓ε02↔ε0  passes through a
minimum and then increases as one moves distally from ε3s↓↓ε01↔ε0 (bottom row), and
those in which the minimum value of ε1h↓↓ε02↔ε0 is achieved at the distal end of
ε3c↓↓ε01↔ε0 (middle row).  The minimum value shown in Figure SIDENDJNS is zero,
which produces a cusp-like ε3s↓↓ε02↔ε0. Notice that case SIDENDJNSa exhibits
the situation described by theorem 6, which guarantees the presence of
the concave segments joining ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0, for
reasonable values of ε1l↓↓ε0i↔ε0 and ε1w↓↓ε0i↔ε0.
.center
(figure SIDENDJNS near here)
    The approach we take for diagnosing joins is similar to that of
theorems 3 to 6. We establish a set of constraints that are satisfied by
the different types of join, and argue that, if the contours in an image
decompose into segments that satisfy these constraints, then they may be
interpreted as two joined generalized cones. If there is only one
decomposition of the contours that satisfies these constraints, then the
interpretation is also unique. Once again, we are not concerned here
with the design of an algorithm for finding the appropriate contour
decomposition, merely with defining its end result.

.twinch 5.0
ε1Theorem 7 (Side-to-end joins).ε0 Let ε1cε0 be a connected contour
bounding the image of two generalized cones ε3sε0↓↓1↔ and
ε3sε0↓↓2↔ connected by a side-to-end join. We assume that the image is
formed from a distant viewpoint chosen such that the viewing direction
lies perpendicular to the plane containing the two cones' axes
ε3cε0↓↓1↔ and ε3cε0↓↓2↔. Assume that ε1cε0 is broken into
segments at points of inflexion. Then there exist two points ε1Pε0 and
ε1Qε0 each of which is either a point of inflexion or lies within a
concave contour segment such that
.br
(i) The line ε1PQε0 lies within the figure bounded by ε1cε0
.br
(ii) ε1PQε0 divides ε1cε0 into two parts ε1cε0↓↓1↔ and
ε1cε0↓↓2↔, between the contour segments or fragments in each of which
there exists a qualitative symmetry whose two axes are the images of
ε3cε0↓↓1↔ and ε3cε0↓↓2↔
.br
(iii) ε1Pε0 and ε1Qε0 minimise the length of contour fragment left
unmatched by these symmetries
.br
(iv) contour fragments in ε1cε0↓↓1↔ left unmatched by the symmetry
round ε3cε0↓↓1↔ would be matched by contour whose proximal parts, and
possibly all of which, lie in the interior of
ε1cε0↓↓2↔ ∪ ε1PQε0; and ε1vice versaε0.
.br
(v) the image of ε3cε0↓↓2↔ intersects ε1PQε0 between ε1Pε0 and ε1Qε0
.br
.twinch 6.0
The proof, which is straightforward, is omitted. The points ε1Pε0 and
ε1Qε0 divide the images of the two cones, and examples of them are
shown in figure SIDENDJNS.
.br
ε1Corollary:ε0 If the points ε1Pε0 and ε1Qε0 are unique, these
constraints determine a unique decomposition of ε1cε0 from which
images of the two axes ε3cε0↓↓i↔ may be recovered.

In practise, it does not matter if ε1Pε0 and ε1Qε0 are not unique
provided that all possible choices give the same axes.

.center
ε1B: Two generalized cones joined end-to-endε0
    If ε3s↓↓ε01↔ε0 or ε3s↓↓ε02↔ε0 contains more than one convex or concave
segment, that cone's axis may be found for segments distal to the join, just as they
were found in figure LONG-AXES for side-to-end joins.  Hence we need consider only
the case where ε3s↓↓ε01↔ε0 and ε3s↓↓ε02↔ε0 have just one segment.

.twinch 5.0
ε1Theorem 8 (End-to-end joins).ε0 Let ε1cε0 be a connected contour
bounding the image of two generalized cones ε3sε0↓↓1↔ and
ε3sε0↓↓2↔ connected by an end-to-end join. We assume that the image is
formed from a distant viewpoint chosen such that the viewing direction
lies perpendicular to the plane containing the two cones' axes
ε3cε0↓↓1↔ and ε3cε0↓↓2↔. Assume that ε1cε0 is broken into
segments at points of inflexion. Then there exist two points ε1Pε0 and
ε1Qε0 either of which may be a point of inflexion, one (but only one)
may lie within a concave segment, and one (but only one) may lie within
a convex segment.
.br
(i) The line ε1PQε0 lies within the figure bounded by ε1cε0
.br
(ii) ε1PQε0 divides ε1cε0 into two parts ε1cε0↓↓1↔ and
ε1cε0↓↓2↔, between the contour segments or fragments in each of which
there exists a qualitative symmetry whose two axes are the images of
ε3cε0↓↓1↔ and ε3cε0↓↓2↔
.br
(iii) ε1Pε0 and ε1Qε0 minimise the length of contour fragment left
unmatched by these symmetries
.br
(iv) contour fragments in ε1cε0↓↓1↔ left unmatched by the symmetry
round ε3cε0↓↓1↔ would be matched by contour whose proximal parts, and
possibly all of which, lie in the interior of
ε1cε0↓↓2↔ ∪ ε1PQε0; and ε1vice versaε0.
.br
(v) the images of ε3cε0↓↓1↔ and ε3cε0↓↓2↔ intersect ε1PQε0
between ε1Pε0 and ε1Qε0
.br
The proof is straightforward.
.twinch 6.0
ε1Corollary:ε0 If the points ε1Pε0 and ε1Qε0 are unique, these
constraints determine a unique decomposition of ε1cε0 from which
images of the two axes ε3cε0↓↓i↔ may be recovered.

Figure ENDJNS shows examples
of the points ε1Pε0 and ε1Qε0 that arise in the different cases. All
inflexion points that occur in the figure have to occur, but in favourable cases
they may not be the only ones.
.center
(figure ENDJNS near here)

.center
ε1Extension to cases where some contour segments are straight linesε0
    In the assumptions ε1R1 - R4ε0 that were made about ε3s↓↓ε01↔ε0 and
ε3s↓↓ε02↔ε0, cases where these surfaces contained straight lines were
excluded out.  Such cases frequently occur in real life, however, and some
examples are shown in figures ENDJNSe and f.  ENDJNSe is a limit of ENDJNSd, and in
some sense also of ENDJNSa; ENDJNSf is a limit of all of the cases.  ENDJNSf may be
solved in the standard way; ε1Pε0 is the only concave point in the contour, and it
matches either the point ε1Qε0, or it induces two "nearest" points ε1Q↓↓ε01↔ε0
and ε1Q↓↓ε02↔ε0 that separate the two arms of the figure from the rectangle
ε1PQ↓↓ε01↔ε0ε1QQ↓↓ε02↔ε0.  Both segmentations are permissible.
     Case ENDJNSe is more difficult.  The only true inflexion points are ε1Q↓↓ε01↔ε0
and ε1Q↓↓ε02↔ε0, but the line ε1Q↓↓ε01↔ε0ε1Q↓↓ε02↔ε0 lies outside the figure.
If ε1Q↓↓ε01↔ε0 and ε1Q↓↓ε02↔ε0 are used
despite this, the segmentation to which they lead corresponds to
thinking of the figure as a rectangle with a piece excised (cf Hollerbach 1975 p. 55).
This would be the preferred description if ε1Q↓↓ε01↔ε0 and ε1Q↓↓ε02↔ε0 lie near
ε1Pε0/↔ε0.  Since ENDJNSe
may be regarded as the limit of ENDJNSd, the point ε1Pε0 (a corner joining two
staight lines) can be regarded as a segmentation point, like the point ε1Pε0
in ENDJNSd.  ε1Pε0 then induces the point ε1Qε0 as shown, which segments
the figure in
the same way as ENDJNSd.  When designing algorithms for dealing with cases
where some lines are nearly straight, "convex" corners often acquire a
dual status that arises from regarding the straight lines as limits of
concave rather than convex contour segments.  This means in practise that straight
lines are somewhat more difficult to deal with than curves since, in the
initial state of the algorithms for implementing the methods defined
here, straight lines and the corners to which they lead may be associated
with several possible labellings.

.center
ε1C: Joins between more than two generalized conesε0
    The principal difference between this and case ε1Bε0 above is
that a given point of segmentation may have more than one match
elsewhere. For example, in the silhouette of an octopus, the deep
concavity between each tentacle matches two others. Also in this case,
it is possible to have end-to-end joins in which both ε1Pε0 and
ε1Qε0 lie within concave contour segments. The only straightforward
result about the case of multiple joins holds when all the joined axes
are coplanar, which is a common but restrictive condition. In this case,
the relevant result is so similar to theorems 7 and 8 that I omit it.

.center
ε2Discussionε0
    The purpose of this article was to elucidate the assumptions that
can reasonably be made when interpreting the occluding contours in an
image. The assumptions at which we arrived were stated as restrictions
ε1R1 - R4ε0, and it was then proved that these restrictions have a
close relationship to the assumption that the viewed surface is composed
of generalized cones. In the second part of the article, we took this
result at face value and studied properties of images of surfaces
constructed in this way. We found that many constraints hold among
portions of the contours in images of such surfaces, and that rough
symmetries are formed around the image of the cones' axes. The
importance of these relations is that one can use them to design
algorithms for finding the generalized cone-based description of a
contour, and for extracting any axes that may be present. By applying
these algorithms repeatedly to the contours found in an image, one can
often derive the 3-D model representation (Marr & Nishihara 1976)) of a
surface's shape without prior knowledge of it. Methods based on the present
theory will however fail for views in which one or more axes are
foreshortened (roughly, whenever the condition ε1l.sin(ε3qε1) > dε0
of page 21 is violated).
    The theory presented in this article is a pure competence theory, or
a theory at the topmost of Marr & Poggio's (1976) four levels. It is
concerned with ends not means.  The natural division between means and ends
is interestingly illustrated by the methods
for segmenting a contour into two component generalized cones (theorems 7 & 8).
The starting-point for our algorithms that actually find the points ε1Pε0 and ε1Qε0
as defined by these theorems is the examination of deep concavities in the
contour ε1cε0 (see Vatan 1976). This contrasts strongly with the theory, because
the concavities may be small or even absent, especially for end-to-end
joins.  Only in certain circumstances
does the underlying theory guarantee their presence (theorem 6).

.single
ε1Acknowledgementε0:  I thank Jennifer Paterson for stylistic criticism,
and Karen Prendergast for preparing the figures.
This report describes research done at the Artificial
Intelligence Laboratory of the Massachusetts Institute of Technology. Support
for the laboratory's artificial intelligence research is provided in part by the
Advanced Research Projects Agency of the Department of Defense under Office
of Naval Research contract N00014-75-C-0643.



.center
ε2Referencesε0

Binford, T. O. (1971)  Visual perception by computer. Presented to the IEEE
Conference on Systems and Control, Miami, in December 1971.

Hollerbach, J. M. (1975) Hierarchical shape description of objects by
selection and modification of prototypes. ε1M. I. T. A. I. Lab.
Technical Report 346ε0.

Marr, D. & Nishihara, H. K. (1976) Representation and recognition of the spatial
organization of three dimensional shapes. (In the press).

Marr, D. & Poggio, T. (1976)  From understanding computation to understanding
neural circuitry. In ε1The visual field: psychophysics and neurophysiology.
Neurosciences Research Program Bulletinε0, E. Poeppel ε1et al.ε0, Eds. (in
the press).

Vatan, P. (1976) ε1M. I. T. Bachelor's Thesis Report.ε0

Vatan, P. & Marr, D. (1976) Algorithms for the segmentation of a contour.
(In preparation).
.end
ββ